package com.wj.graph;

import com.wj.linear.Stack;

/**
 * @author wen.jie
 * @date 2021/8/27 17:10
 */
public class DepthFirstOrder {

    private boolean[] marked;

    private Stack<Integer> reversePost;

    public DepthFirstOrder(Digraph G){

        //校验是否有环
        if(new DirectedCycle(G).hasCycle())
            throw new RuntimeException("Digraph hasCycle!");

        this.marked = new boolean[G.V()];
        this.reversePost = new Stack<>();

        //找到图中每一个顶点，让每一个顶点作为入口，调用dfs搜索
        for (int v = 0; v < G.V(); v++) {
            if (!marked[v])
                dfs(G, v);
        }
    }

    private void dfs(Digraph G, int v) {
        marked[v] = true;
        for (Integer w : G.adj(v)) {
            //如果当前顶点w没有搜索,则递归调用dfs进行搜索
            if (!marked[w])
                dfs(G, w);
        }
        reversePost.push(v);
    }

    public Stack<Integer> reversePost() {
        return reversePost;
    }

}
